#include <bits/stdc++.h>

/*
 * 单源最短路径问题，
 * Dijstra算法
 *
 *
 */
const int maxint = 99999;  // 自定义一个极大数

template <class Type>
// n:n个顶点，v：源点，dist[]：dist[i]表示i结点对应的最短特殊路径长度，
// prev[]：prev[i]表示i结点的上一个结点，c[][]： 权值
void Dijstra(int n, int v, Type dist[], int prev[], Type **c) {
  // 初始化 s[], dist[], prev[]
  bool *s = (bool *)malloc(sizeof(bool) * (n + 1));
  for (int i = 1; i <= n; i++) {
    dist[i] = c[v][i];
    s[i] = false;
    if (dist[i] == maxint) {
      prev[i] = 0;  // 上一个结点为0，表示不可直接到达
    } else {
      prev[i] = v;  //  上一个结点为v
    }
  }
  dist[v] = 0;
  s[v] = true;  // 将v结点加入集合S

  // 第一层for，n个节点需要迭代n次;
  // 第二层for，遍历 V-S中的结点，依次将 V-S中的结点加入到 S
  // 第三层for，向 S中添加新的结点后，需要马上更新 dist[]和 prev[]
  for (int i = 1; i <= n; i++) {
    int temp = maxint;
    int u = v;
    // 遍历V-S中的结点，找出最短路径结点及最短路径
    for (int j = 1; j <= n; j++) {
      // 如果j结点不在集合S中（即在V-S中），并且距离更短
      if ((!s[j]) && (dist[j]) < temp) {
        u = j;           // 记录该节点
        temp = dist[j];  // 记录当前距离
      }
    }
    s[u] = true;  // 将u结点加入到集合S

    // 将u加入集合S中后，需要及时更新 dist[]和prev[]
    for (int k = 1; k <= n; k++) {
      // k结点属于集合S-v，且u能到达k，才需要更新
      if ((!s[k]) && (c[u][k] < maxint)) {
        Type newdist = dist[u] + c[u][k];
        if (newdist < dist[k]) {
          dist[k] = newdist;
          prev[k] = u;
        }
      }
    }
  }
}

void displayPath(int n, int prev[]) {
  if (prev[n] == 0) {
    printf("%d", n);
    return;
  }
  displayPath(prev[n], prev);
  printf("--> %d", n);
}

int main() {
  int n;  // n个节点
  int dist[100] = {0}, prev[100] = {0};
  scanf("%d", &n);
  // 动态生成二维指针
  int **c = (int **)malloc(sizeof(int *) * (n + 1));
  for (int i = 0; i <= n; i++) {
    c[i] = (int *)malloc(sizeof(int) * (n + 1));
    // 手动赋初始值为极大值，memset函数无法满足要求
    for (int j = 0; j <= n; j++) {
      c[i][j] = maxint;
    }
  }
  // 数据录入：m条边，结点 i到结点 j的权重为 w
  int m;
  scanf("%d", &m);
  for (int k = 1; k <= m; k++) {
    int i, j, w;
    scanf("%d %d %d", &i, &j, &w);
    c[i][j] = w;
  }

  int root;
  scanf("%d", &root);
  Dijstra<int>(n, root, dist, prev, c);

  for (int i = 1; i <= n; i++) {
    printf("源点：%d，目标点：%d，距离：%d，", root, i, dist[i]);
    printf("路径：");
    displayPath(i, prev);
    printf("\n");
  }
  return 0;
}
